import math
import algorithm

class Solution1:
    def crackSafe(self, n: int, k: int) -> str:
        if n == 1:
            return ''.join(str(i) for i in range(k))
        if k == 1:
            return '0' * n

        def edge_id(lst):
            node = 0
            for x in lst:
                node *= k
                node += x
            return node

        back_track = []
        visited = [False] * int(math.pow(k, n))

        def dfs(node):
            #print(node)
            for i in range(k):
                edge = node + [i]
                edge_id = edge_id(edge)
                if not visited[edge_id]:
                    next_node = edge[1:]
                    visited[edge_id] = True
                    dfs(next_node)
            back_track.append(node)

        dfs([0] * (n-1))
        node_lst = back_track[::-1]
        #print([x for x in node_lst])
        res = ''
        for x in node_lst[0][1:]:
            res += str(x)
        for node in node_lst:
            res += str(node[-1])
        return res


class UnionFindSet:
    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1] * n

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return True  # cycle detected
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]
        return False


def directed_graph_find_eulerian_path(n, adj, indegrees, outdegrees):
    def find_source_node():
        ufs = UnionFindSet(n)
        for u in range(n):
            for v in adj[u]:
                ufs.union(u, v)
        connected = sum(1 for u in range(n) if u == ufs.parents[u])
        if not connected:
            return None
        if indegrees == outdegrees:
            return 0
        degrees = [x - y for x, y in zip(indegrees, outdegrees)]
        if all(x in [-1,0,1] for x in degrees):
            if degrees.count(-1) == 1 and degrees.count(1) == 1:
                return degrees.index(-1)

    path = []
    def dfs_visit(u):
        while adj[u]:
            v = adj[u].pop()
            dfs_visit(v)
        path.append(u)

    s = find_source_node()
    if s is None:
        return None
    dfs_visit(s)
    path.reverse()
    return path


class Solution2:
    def crackSafe(self, n: int, k: int) -> str:
        if n == 1:
            return ''.join(str(x) for x in range(k))
        n_nodes = k ** (n-1)

        def int2lst(x):
            lst = []
            for i in range(n-1):
                lst.append(x % k)
                x //= k
            lst.reverse()
            return lst

        def lst2int(lst):
            x = 0
            for i in range(n-1):
                x *= k
                x += lst[i]
            return x

        adj = [None] * n_nodes
        indegrees = [k] * n_nodes
        outdegrees = [k] * n_nodes
        for u in range(n_nodes):
            adj[u] = [lst2int(int2lst(u)[1:] + [v]) for v in range(k)]

        path = directed_graph_find_eulerian_path(n_nodes, adj, indegrees, outdegrees)
        string = int2lst(0)
        for u, v in zip(path[:-1], path[1:]):
            string.append(int2lst(v)[-1])
        string = ''.join(str(x) for x in string)
        return string


solution = Solution2()
xx = solution.crackSafe(1, 2)
print(xx)
print(len(xx))

